/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void printVec(vector<int> v)
{
	for(auto it = v.begin();it != v.end() ;++it)
		cout<<*it<<',';
	cout<<endl;
}
class Solution {
public:
    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
    	// cout<<"pre:"<<endl;
    	// printVec(pre);
    	// cout<<"in:"<<endl;
    	// printVec(in);
    	if(pre.size() != in.size() || pre.size() == 0)
    		return nullptr;
    	if(pre.size() == 1)
    		return new TreeNode(pre[0]);
    	int val = pre[0];
    	auto idx = std::find(in.begin(),in.end(),val);
    	int cnt = idx - in.begin();
    	// cout<<cnt<<endl;
    	TreeNode *node = new TreeNode(val);
    	node->left = reConstructBinaryTree(vector<int>(pre.begin()+1,pre.begin() +1 +cnt),vector<int>(in.begin(),in.begin() + cnt));
    	// cout<<"node->right"<<endl;
    	node->right = reConstructBinaryTree(vector<int>(pre.begin() +1 + cnt, pre.end()),vector<int>(in.begin()+cnt+1,in.end()));
    	return node;
    }
};

void printTree(TreeNode *head)
{
	if(head)
	{
		cout<<head->val<<endl;
		printTree(head->left);
		printTree(head->right);
	}
}
int main()
{	
	Solution s;

	vector<int> v1{1,2,3,4,5,6,7},v2{3,2,4,1,6,5,7};
	
	TreeNode *head = s.reConstructBinaryTree(v1,v2);
	printTree(head);
	return 0;
}